#include <stdio.h>
#include <stdlib.h>

#include "max_heap.h"

static int __maxheap_Extend(MAX_HEAP_S* pstMaxHeap)
{
    void** ppNodes = (void**)realloc(pstMaxHeap->ppNodes, sizeof(void*) * pstMaxHeap->ulCapacity * 2);
    if (ppNodes == NULL)
    {
        return -1;
    }

    pstMaxHeap->ppNodes = ppNodes;

    return 0;
}

int MAXHEAP_Init(MAX_HEAP_S* pstMaxHeap, size_t ulInitCapacity, MAXHEAP_CMP_NODE_PF pfCmp)
{
    void** ppNodes = (void**)malloc(sizeof(void*)*ulInitCapacity);
    if (ppNodes == NULL)
    {
        return -1;
    }

    pstMaxHeap->ppNodes = ppNodes;
    pstMaxHeap->ulCapacity = ulInitCapacity;
    pstMaxHeap->ulSize = 0;
    pstMaxHeap->pfCmp = pfCmp;

    return 0;
}

void MAXHEAP_Fini(MAX_HEAP_S* pstMaxHeap)
{
    if (pstMaxHeap != NULL && pstMaxHeap->ppNodes)
    {
        free(pstMaxHeap->ppNodes);

        pstMaxHeap->ppNodes = NULL;
        pstMaxHeap->ulCapacity = 0;
        pstMaxHeap->ulSize = 0;
        pstMaxHeap->pfCmp = NULL;
    }
}

int MAXHEAP_Push(MAX_HEAP_S* pstMaxHeap, void* pNode)
{
    if (pstMaxHeap->ulSize == pstMaxHeap->ulCapacity)
    {
       return __maxheap_Extend(pstMaxHeap);
    }

    size_t ulNewIndex = pstMaxHeap->ulSize;
    size_t ulParentIdx = (ulNewIndex - 1) / 2;

    while (ulNewIndex > 0 && pstMaxHeap->pfCmp(pNode, pstMaxHeap->ppNodes[ulParentIdx]) > 0)
    {
        pstMaxHeap->ppNodes[ulNewIndex] = pstMaxHeap->ppNodes[ulParentIdx];
        ulNewIndex = ulParentIdx;
        ulParentIdx = (ulNewIndex - 1) / 2;
    }

    pstMaxHeap->ppNodes[ulNewIndex] = pNode;
    pstMaxHeap->ulSize++;

    return 0;
}

void MAXHEAP_Show(MAX_HEAP_S* pstMaxHeap)
{
    for (size_t ulIdx = 0; ulIdx < pstMaxHeap->ulSize; ulIdx++)
    {
        printf("%d ", (int)(long)pstMaxHeap->ppNodes[ulIdx]);
    }

    printf("\n");
}

void* MAXHEAP_Pop(MAX_HEAP_S* pstMaxHeap)
{
    if (pstMaxHeap->ulSize == 0)
    {
        return NULL;
    }

    void* pTop = pstMaxHeap->ppNodes[0];
    pstMaxHeap->ppNodes[0] = pstMaxHeap->ppNodes[pstMaxHeap->ulSize - 1];
    pstMaxHeap->ulSize--;

    size_t ulIdx = 0;
    size_t ulLeftIdx = 2 * ulIdx + 1;
    size_t ulRightIdx = ulLeftIdx + 1;
    
    while (ulLeftIdx < pstMaxHeap->ulSize)
    {
        size_t ulMaxIdx = ulIdx;
        if (pstMaxHeap->pfCmp(pstMaxHeap->ppNodes[ulLeftIdx], pstMaxHeap->ppNodes[ulMaxIdx]) > 0)
        {
            ulMaxIdx = ulLeftIdx;
        }
        
        if (ulRightIdx < pstMaxHeap->ulSize && 
            pstMaxHeap->pfCmp(pstMaxHeap->ppNodes[ulRightIdx], pstMaxHeap->ppNodes[ulMaxIdx]) > 0)
        {
            ulMaxIdx = ulRightIdx;
        }

        if (ulMaxIdx == ulIdx)
        {
            break;
        }

        void* pTmp = pstMaxHeap->ppNodes[ulIdx];
        pstMaxHeap->ppNodes[ulIdx] = pstMaxHeap->ppNodes[ulMaxIdx];
        pstMaxHeap->ppNodes[ulMaxIdx] = pTmp;
        ulIdx = ulMaxIdx;

        ulLeftIdx = 2 * ulIdx + 1;
        ulRightIdx = ulLeftIdx + 1;
    }

    return pTop;
}

int __CmpNode(void* pNode1, void* pNode2)
{
    int iNode1 = (int)(long)pNode1;
    int iNode2 = (int)(long)pNode2;

    return iNode1 - iNode2;
}

#if 0
int main(int argc, char** argv)
{
    MAX_HEAP_S stMinHeap;

    MAXHEAP_Init(&stMinHeap, 8, __CmpNode);

    int iValue = 8;
    MAXHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 2;
    MAXHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 6;
    MAXHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 4;
    MAXHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 3;
    MAXHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 9;
    MAXHEAP_Push(&stMinHeap, (void*)(long)iValue);

    iValue = 7;
    MAXHEAP_Push(&stMinHeap, (void*)(long)iValue);

    MAXHEAP_Show(&stMinHeap);

    void* pData = MAXHEAP_Pop(&stMinHeap);
    while (pData != NULL)
    {
        MAXHEAP_Show(&stMinHeap);
        //printf("%d ", (int)(long)pData);
        pData = MAXHEAP_Pop(&stMinHeap);
    }

    printf("\n");

    return 0;
}
#endif